5107. Minibus

 

Minibus in Mendeleevo city moves according to the route from the bus stop number 1 to the bus stop number m. The driver stops at the station only if at least one of the passengers in the cabin wants to get out. At the same time all the passengers waiting for a minibus at this stop, sit in it (number of seats is unlimited). As the bus starts moving from the stop number 1, all passengers at it just sit down in a minibus.

Given the list of passengers, determine the list of stations where the bus stops. It is guaranteed that at least one passenger of minibus waits at the bus stop number 1.

 

Input. First line contains two positive integers n, m (1 ≤ n ≤ 105, 1 ≤ m ≤ 109)the number of passengers and bus stops. Each of the next n lines contains two positive integers li – the number of bus stop where the i-th passenger waits for minibus, ri – the number of bus stop where the i-th passenger goes out (1 ≤ li < rim).

 

Output. Print in the first line the number of bus stops k where the minibus will stop. Then print k lines – the numbers of these bus stops in increasing order.

 

Sample input

Sample output

6 11

1 4

2 3

4 5

2 5

4 7

4 10

5

1

4

5

7

10

 

 

SOLUTION

graphs

 

Algorithm analysis

Construct a directed graph, which vertices are stops, and the edges are passengers connecting the vertices li and ri. Since the number of vertices in the graph (stops) is m ≤ 109, and the graph is sparse (the number of edges is n ≤ 105), then the adjacency list g is given by the structure map<int,vector<int> > g – each vertex is assigned an adjacency list stored in the vector. To remember the visited vertices, well use the set set<int> as the used structure.

 

Run the depth-first search from the vertex 1. The vertices that will be visited (that will be added to used) are the numbers of stops where the minibus will stop.

 

 

Algorithm realization

Declare an adjacency list of the graph g, as well as the set of visited vertices used.

 

set<int> used;

set<int>::iterator iter;

map<int,vector<int> > g;

 

Depth first search from the vertex v.

 

void dfs(int v)

{

 

Mark the vertex v to be used.

 

  used.insert(v);

 

Iterate the vertices, adjacent to v.

 

  for(int i = 0; i < g[v].size(); i++)

  {

 

Graph contains the edge (v, to).

 

    int to = g[v][i];

 

If the vertex to is not visited, run depth first search from to.

 

    if(used.find(to) == used.end()) dfs(to);

  }

}

 

The main part of the program. Read the input data, construct the graph.

 

scanf("%d %d",&n,&m);

for(i = 0; i < n; ++i)

{

  scanf("%d %d",&x,&y);

  g[x].push_back(y);

}

 

Run depth first search from the vertex 1.

 

dfs(1);

 

Print the list of visited vertices – the numbers of stops where the minibus will stop.

 

printf("%d\n",used.size());

for(iter = used.begin(); iter != used.end(); iter++)

  printf("%d\n",*iter);